//单链表

//编译指令，头文件可只编译一次
#pragma once

//单链表的类型定义
template <typename E>
struct LNode
{
    //数据域
    E data;
    //指针域
    LNode*next;
};
//LNode是个模板   单链表指针类型
template <typename E>
using LinkList = LNode<E> *;

//初始化空表InitList（&L）
template <typename E>
void InitList(LinkList<E> &L)
{
    L=new LNode<E>;
    L->next=nullptr;//表示空指针 0,null,头节点没有用处，指针域为空
}

//销毁单链表DestoryList(&L)  就是把所有节点释放掉
template <typename E>
void DestoryList(LinkList <E> &L)
{
    LinkList <E> p=L;
    while(L)//不空
    {
        p=L;//用p把l节点记录下来
        L=L->next;
        delete p;
    }
}

//单链表插入ListInsert(&L,i,e)
template <typename E>
void ListInsert(LinkList <E> &L,int i,E e)
{
    //首先找到第i-1个节点p
    LinkList <E> p=L;//p为LinkList类型
    int j=0;
    while(p && j<i-1)
    {
        p=p->next;
        j++;
    }
    //在p之后插入e
    if (p&&j==i-1)
    {
        //新建节点
        LinkList <E> s=new LNode<E>;
        s->data=e;
        s->next=p->next;
        p->next=s;
        //new LNode<E>{e,p->next};
        //p->next=s;
    }
    else {
        throw "i out of range";
    }
}

//单链表删除ListDelete(&L,i,e)  删除第i个元素，用e返回
template <typename E>
void ListDelete(LinkList <E> &L,int i,E &e)
{
    //找到第i-1个节点
    auto p=L;
    int j=0;
    while (p && j<i-1)
    {
        p=p->next;
        j++;
    }
    //删除第i个节点
    if (p && j==i-1 && p->next)
    {
        //首先把p的next记录下来
        auto q=p->next;
        p->next =q->next;
        e=q->data;
        delete q;
    }
    else {
        throw "i out of range";
    }
}